package com.shuang.string7;

public class RepeatedSubstringPattern {

    /*
     * 如果字符串s是由重复子串组成的，s字符串减去 它的最长相等的前后缀构成的子串所剩下的子串 一定是s的最小重复子串。
     *
     * 推得：当字符串s的长度 可以整除 剩下的子串时，剩下的子串 就是s的最小重复子串。
     *
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public boolean repeatedSubstringPattern(String s) {
        //KMP算法

        //字符串长度
        int len = s.length();

        //next数组
        int[] next = new int[len];

        //初始化数组
        next[0] = 0;

        //初始化 要退回的索引 同时也是数组要赋予的值 即最长相等前后缀的长度
        int i = 0;

        //构建KMP算法的前缀表
        for (int j = 1; j < len; j++) {

            //不匹配的情况
            while (i > 0 && s.charAt(i) != s.charAt(j)) {
                i = next[i - 1];
            }

            //匹配
            if (s.charAt(i) == s.charAt(j)) {
                i++;
            }

            next[j] = i;
        }

        //判断重复子字符串 能整除则是
        if (next[len - 1] > 0 && len % (len - next[len - 1]) == 0) {
            return true;
        }

        return false;

    }
}
